Corelab Seminar
2017-2018
Vangelis Markakis
Fairness with indivisible goods: solution concepts and algorithms
Abstract.
Fair division typically involves the allocation of a set of resources to a set of agents, so that certain fairness criteria are achieved. Over the years, fair division problems have attracted the attention of various scientific disciplines including among others, mathematics, economics, computer science, and political science. A notable qualitative distinction in the models that have been used concerns the nature of the resources and whether they are divisible or indivisible. Indeed, even though most fairness notions are guaranteed to exist under divisible items, this is no longer the case in the presence of indivisibilities. To make it worse, decent approximation algorithms are also unlikely to exist for the most standard and oldest fairness notions that have been proposed, such as envy-freeness and proportionality.
The purpose of this tutorial is to give an overview of fairness concepts that have been studied in the more recent years and seem to be more appropriate for the context of indivisible items. Among others, these include maximin share fairness, envy-freeness up to one item, envy-freeness up to any item, and related variants. These concepts tend to be more amenable to efficient algorithms, than the more traditional fairness notions, and after the relevant definitions, we will discuss the currently known algorithmic results for each of them. Our focus will be on both exact and approximation algorithms, highlighting also certain special cases. Finally, the last part of the tutorial will also discuss mechanism design aspects of these problems. We will conclude with many interesting open problems that stem from this line of research.